package com.formula.datastructure.exercise.sort.basic;

import com.formula.datastructure.util.DataUtil;

public class BubbleSort {
    public Integer[] sort(Integer[] array) {
        Integer temp;
        int size = array.length;
        /**
         * 两个for
         * 第一个for有两个作用，一是跑n-1轮，二是限定end
         */
        for (int i = size - 1; i > 0; i--) {
            // 这个非常有用, 可以优化速度
            int flag = 0;
            for (int j = 0; j < i; j++) {
                if (array[j] > array[j + 1]) {
                    flag = 1;
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            // 一轮下来没有交换, 说明已经排好序
            if(flag == 0){
                return array;
            }
        }
        return array;
    }

    public static void main(String[] args) {
        BubbleSort bubble = new BubbleSort();
        Integer[] array = DataUtil.genUniqueArray(20, 100);
        DataUtil.printIndex(20);
        DataUtil.printArray(array);
        DataUtil.printArray(bubble.sort(array));
    }
}
